{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #找树左下角的值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findBottomLeftValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找树左下角的值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树的 <strong>根节点</strong> <code>root</code>，请找出该二叉树的&nbsp;<strong>最底层&nbsp;最左边&nbsp;</strong>节点的值。</p>\n",
    "\n",
    "<p>假设二叉树中至少有一个节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2020/12/14/tree1.jpg\" style=\"width: 182px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = [2,1,3]\n",
    "<strong>输出: </strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2: </strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2020/12/14/tree2.jpg\" style=\"width: 242px; \" /><strong> </strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>[1,2,3,4,null,5,6,null,null,7]\n",
    "<strong>输出: </strong>7\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点个数的范围是 <code>[1,10<sup>4</sup>]</code></li>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>-2<sup>31</sup>&nbsp;&lt;= Node.val &lt;= 2<sup>31</sup>&nbsp;- 1</code>&nbsp;</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 513&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/find-bottom-left-tree-value/\">https://leetcode-cn.com/problems/find-bottom-left-tree-value/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [LwUNpT](https://leetcode.cn/problems/LwUNpT/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [LwUNpT](https://leetcode.cn/problems/LwUNpT/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        leftmost_value_at_depth = dict() # 深度为索引，存放节点的值\n",
    "        max_depth = -1\n",
    "        queue = deque([(root, 0)])\n",
    "        while queue:\n",
    "            node, depth = queue.popleft()\n",
    "            if node is not None:\n",
    "                max_depth = max(max_depth, depth)\n",
    "                leftmost_value_at_depth[depth] = node.val\n",
    "                queue.append((node.right, depth + 1))\n",
    "                queue.append((node.left, depth + 1))\n",
    "        return leftmost_value_at_depth[max_depth]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        nl = [root]\n",
    "        ans = root.val\n",
    "        while nl:\n",
    "            tmp = []\n",
    "            f = 0\n",
    "            for node in nl:\n",
    "                if f == 0:\n",
    "                    if node.left:\n",
    "                        ans = node.left.val\n",
    "                        f = 1\n",
    "                    elif node.right:\n",
    "                        ans = node.right.val\n",
    "                        f = 1\n",
    "                if node.left:\n",
    "                    tmp.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp.append(node.right)\n",
    "            nl = tmp[:]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        # 后序遍历写法\n",
    "        # def get_height(node):\n",
    "        #     leftheight = get_height(node.left) if node.left else 0\n",
    "        #     rightheight = get_height(node.right) if node.right else 0\n",
    "        #     return max(leftheight,rightheight)+1\n",
    "        # height = get_height(root)\n",
    "        # print(height)\n",
    "        \n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        # cnt = 0\n",
    "        res = 0\n",
    "        while queue:\n",
    "            # cnt += 1\n",
    "            n = len(queue)\n",
    "\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()\n",
    "                if i == 0:\n",
    "                    res = node.val\n",
    "                # print(node,cnt)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "            ans = node.val\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        node = TreeNode()\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        nl = [root]\n",
    "        ans = root.val\n",
    "        while nl:\n",
    "            tmp = []\n",
    "            f = 0\n",
    "            for node in nl:\n",
    "                if f == 0:\n",
    "                    ans = node.val\n",
    "                    f = 1\n",
    "                if node.left:\n",
    "                    tmp.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp.append(node.right)\n",
    "            nl = tmp[:]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            ans = tmp[0].val\n",
    "            for node in tmp:\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        q = [root]\n",
    "        ans = 0\n",
    "        while len(q) > 0:\n",
    "            n = len(q)\n",
    "            for i in range(n):\n",
    "                cur = q.pop(0)\n",
    "                if i == 0:\n",
    "                    ans = cur.val\n",
    "                if cur.left is not None:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right is not None:\n",
    "                    q.append(cur.right)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        def bfs():\n",
    "            while queue:\n",
    "                for node in queue:\n",
    "                    if node:\n",
    "                        self.res = node.val\n",
    "                        break\n",
    "                for i in range(len(queue)):\n",
    "                    root = queue.pop(0)\n",
    "                    if root.left:\n",
    "                        queue.append(root.left)\n",
    "                    if root.right:\n",
    "                        queue.append(root.right)\n",
    "        queue = [root]\n",
    "        self.res = None\n",
    "        bfs()\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        stack = [root]\n",
    "        while True:\n",
    "            temp = []\n",
    "            for cur in stack:\n",
    "                if cur.left:    temp.append(cur.left)\n",
    "                if cur.right:   temp.append(cur.right)\n",
    "            if not temp:\n",
    "                return stack[0].val\n",
    "            else:\n",
    "                stack = temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right: q.append(node.right)\n",
    "            if node.left: q.append(node.left)\n",
    "        return node.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        queue=[root]\n",
    "        result=TreeNode(0)\n",
    "        while queue:\n",
    "            size=len(queue)\n",
    "            for i in range(size):\n",
    "                temp=queue.pop(0)\n",
    "                if temp.right:\n",
    "                    queue.append(temp.right)\n",
    "                if temp.left:\n",
    "                    queue.append(temp.left)\n",
    "\n",
    "            result=temp\n",
    "        return result.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        que = deque()\n",
    "        if root:\n",
    "            que.append(root)\n",
    "        ans = []\n",
    "        while len(que):\n",
    "            nodes = []\n",
    "            size = len(que)\n",
    "            for i in range(size):\n",
    "                node = que.popleft()\n",
    "                nodes.append(node.val)\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "            ans.append(nodes)\n",
    "        return ans[-1][0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return \n",
    "        ##\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            res = node.val \n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        q = Queue()\n",
    "        q.put(root)\n",
    "        while not q.empty():\n",
    "            node = q.get()\n",
    "            if node.right:\n",
    "                q.put(node.right)\n",
    "            if node.left:\n",
    "                q.put(node.left)\n",
    "            res = node.val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        # 队列初始化为第一层, 即根节点\n",
    "        q = [root]\n",
    "        res = root.val\n",
    "        while q:\n",
    "            # 记录当前层的节点个数curlen\n",
    "            curlen = len(q)\n",
    "            # 更新res为当前层最左侧的值\n",
    "            res = q[0].val\n",
    "            # 只遍历当前层的节点, 即前curlen个\n",
    "            for node in q[:curlen]:\n",
    "                # 左右子节点非空时, 将其追加到队列中\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            # 将队列更新成下一层的节点\n",
    "            q = q[curlen:]\n",
    "        # 最终res就是最底层最左侧的值\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        ans = []\n",
    "        while q:\n",
    "            vals = []\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                vals.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "            ans.append(vals)\n",
    "        return ans[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return None\n",
    "        # 层序遍历， bottomleft存储每一层最左端的节点值\n",
    "        q = [root]\n",
    "        bottomleft = []\n",
    "        while q:\n",
    "            temp = q\n",
    "            q = []\n",
    "            for index,node in enumerate(temp):#遍历当前层\n",
    "                if index==0:\n",
    "                    bottomleft.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        # print(bottomleft)\n",
    "        return bottomleft[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        from collections import deque\n",
    "\n",
    "        res = 0\n",
    "        que = deque()\n",
    "        que.append(root)\n",
    "        while que:\n",
    "            tmp = que.popleft()\n",
    "            if not tmp:\n",
    "                continue\n",
    "            res = tmp.val\n",
    "            que.append(tmp.right)\n",
    "            que.append(tmp.left)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        start = [root]\n",
    "        res = []\n",
    "        while start:\n",
    "            nxt = []\n",
    "            tmp = []\n",
    "            for node in start:\n",
    "                if not node:\n",
    "                    continue\n",
    "                tmp.append(node.val)\n",
    "                if node.left:\n",
    "                    nxt.append(node.left)\n",
    "                if node.right:\n",
    "                    nxt.append(node.right)\n",
    "            if tmp:\n",
    "                res = tmp\n",
    "            start = nxt\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        que = deque()\n",
    "        if root:\n",
    "            que.append(root)\n",
    "        ans = []\n",
    "        while len(que):\n",
    "            nodes = []\n",
    "            size = len(que)\n",
    "            for i in range(size):\n",
    "                node = que.popleft()\n",
    "                nodes.append(node.val)\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "            ans.append(nodes)\n",
    "        return ans[-1][0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        # 层序遍历, 找到最下一层的左叶子节点的值\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        from collections import deque\n",
    "        res = 0\n",
    "        stack = deque([root])\n",
    "        while stack:\n",
    "            for i in range(len(stack)):\n",
    "                cur = stack.popleft()   # 弹出当前节点\n",
    "                if i == 0:  # 每一层的第一个节点\n",
    "                    res = cur.val\n",
    "                if cur.left:\n",
    "                    stack.append(cur.left)\n",
    "                if cur.right:\n",
    "                    stack.append(cur.right)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        if not root: return -1\n",
    "        node = TreeNode()\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        queue, res = [root], root.val\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            if queue:\n",
    "                res = queue[0].val\n",
    "\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    tmp.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp.append(node.right)\n",
    "            queue = tmp\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        max_dep = 0\n",
    "        res_val = root.val\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        \n",
    "        while queue:\n",
    "            pilot = queue[0]\n",
    "            queue.popleft()\n",
    "            if pilot.right:\n",
    "                queue.append(pilot.right)\n",
    "            if pilot.left:\n",
    "                queue.append(pilot.left)\n",
    "        return pilot.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        stack = [(root, 0, 0)]\n",
    "        maxl, maxd = -10**4, 0\n",
    "        v = 0\n",
    "        while stack:\n",
    "            node, l, d = stack.pop()\n",
    "            if d > maxd:\n",
    "                maxl, maxd = l, d\n",
    "                v = node.val\n",
    "            elif d == maxd and l > maxl:\n",
    "                maxl = l\n",
    "                v = node.val\n",
    "            if node.left:\n",
    "                stack.append((node.left, l+1, d+1))\n",
    "            if node.right:\n",
    "                stack.append((node.right, l-1, d+1))\n",
    "        return v\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "\n",
    "        # level tranverse\n",
    "\n",
    "        cur = [root]\n",
    "\n",
    "        while cur:\n",
    "            next = []\n",
    "            ret = cur[0]\n",
    "            for n in cur:\n",
    "                if n.left:\n",
    "                    next.append(n.left)\n",
    "                \n",
    "                if n.right:\n",
    "                    next.append(n.right)\n",
    "            \n",
    "            cur = next\n",
    "        \n",
    "        return ret.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "\n",
    "        res = 0\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            tmp = stack.pop(0)\n",
    "            if not tmp:\n",
    "                continue\n",
    "            res = tmp.val\n",
    "            stack.append(tmp.right)\n",
    "            stack.append(tmp.left)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        g = [root]\n",
    "        ans = root.val\n",
    "        while g:\n",
    "            ans = g[0].val\n",
    "            ng = []\n",
    "            for x in g:\n",
    "                if x.left: ng.append(x.left)\n",
    "                if x.right: ng.append(x.right)\n",
    "            g = ng\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = 0\n",
    "        while queue:\n",
    "            cur_node = queue.popleft()\n",
    "            res = cur_node.val\n",
    "            if cur_node.right: queue.append(cur_node.right)\n",
    "            if cur_node.left: queue.append(cur_node.left)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right: q.append(node.right)\n",
    "            if node.left: q.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root):\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            root = queue.pop(0)\n",
    "            if root.right:\n",
    "                queue.append(root.right)\n",
    "            if root.left:\n",
    "                queue.append(root.left)\n",
    "        return root.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        q=collections.deque([root])\n",
    "        while q:\n",
    "            node=q.popleft()\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "            ans=node.val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        #层序遍历\n",
    "        ans=[]\n",
    "        deque=collections.deque([root])\n",
    "        while deque:\n",
    "            temp=[]\n",
    "            for _ in range(len(deque)):\n",
    "                node=deque.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left:\n",
    "                    deque.append(node.left)\n",
    "                if node.right:\n",
    "                    deque.append(node.right)\n",
    "            ans.append(temp)\n",
    "        return ans[-1][0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        value = root.val\n",
    "        max_level = 0\n",
    "        q, head = [root], -1\n",
    "        level = [0]\n",
    "        while head < len(q) - 1:\n",
    "            head += 1\n",
    "            for node in [q[head].left, q[head].right]:\n",
    "                if node is not None:\n",
    "                    q.append(node)\n",
    "                    level.append(level[head] + 1)\n",
    "                    if level[-1] > max_level:\n",
    "                        max_level = level[-1]\n",
    "                        value = node.val\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            ll = len(q)\n",
    "            v = -float('inf')\n",
    "            while ll:\n",
    "                ll -= 1\n",
    "                cur = q.popleft()\n",
    "                if v == -float('inf'):\n",
    "                    v = cur.val\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            if not q:\n",
    "                return v\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        v = 0\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            v = node.val\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "        return v\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            layer_len = len(q)\n",
    "            temp = deque(q)\n",
    "            for _ in range(layer_len):\n",
    "                cur = q.popleft()\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "        \n",
    "        return temp[-1].val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        #copy 0x3\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right: q.append(node.right)\n",
    "            if node.left:  q.append(node.left)\n",
    "        return node.val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "         ans=[]\n",
    "         q=deque()\n",
    "         q.append(root)\n",
    "         while q:\n",
    "            l=[]\n",
    "            for _ in range(len(q)):\n",
    "               \n",
    "               node=q.popleft()\n",
    "               l.append(node.val)\n",
    "              \n",
    "               if node.left:\n",
    "                     q.append(node.left)\n",
    "               if node.right:\n",
    "                     q.append(node.right)\n",
    "            ans.append(l)\n",
    "         return ans[-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return None \n",
    "        \n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "        \n",
    "        res = None \n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                node = queue.pop(0)\n",
    "                if i == 0:\n",
    "                    res = node.val \n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        result = 0\n",
    "        qa = deque()\n",
    "        qb = deque()\n",
    "\n",
    "        qa.appendleft(root)\n",
    "        while len(qa) > 0 or len(qb) > 0:\n",
    "            result = qa[-1].val\n",
    "            while len(qa) > 0:\n",
    "                node = qa.pop()\n",
    "                if node.left:\n",
    "                    qb.appendleft(node.left)\n",
    "                if node.right:\n",
    "                    qb.appendleft(node.right)\n",
    "            t = qa\n",
    "            qa = qb\n",
    "            qb = t\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        bottom_left = root.val\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()\n",
    "                if i == 0:\n",
    "                    bottom_left = node.val\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return bottom_left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        if root==None:\n",
    "            return []\n",
    "        q = deque([root])\n",
    "        res = 0\n",
    "        while q:\n",
    "            tmp = len(q)\n",
    "            for i in range(tmp):\n",
    "                node = q.popleft()\n",
    "                if i==0:\n",
    "                    res = node.val\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        dq = deque([root])\n",
    "        while dq:\n",
    "            node = dq.popleft()\n",
    "            if node.right: dq.append(node.right)\n",
    "            if node.left: dq.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        #imitate\n",
    "        q= deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        #imitate\n",
    "        #关于树的题目，可以通过遍历顺序找到想要的值，这里从上到下，从右到左，找到了。广义的bfs\n",
    "        q= deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "        return node.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        queue = deque()\n",
    "        current_idx = 0\n",
    "        queue.append((root, current_idx))\n",
    "\n",
    "        ret_list = []\n",
    "        while queue:\n",
    "            node, idx = queue.popleft()\n",
    "            if idx != current_idx:\n",
    "                current_idx = idx\n",
    "                ret_list = [node.val]\n",
    "            else:\n",
    "                ret_list.append(node.val)\n",
    "            if node.left:\n",
    "                queue.append((node.left, idx + 1))\n",
    "            if node.right:\n",
    "                queue.append((node.right, idx + 1))\n",
    "        return ret_list[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        num=root.val\n",
    "        que1=deque()\n",
    "        que2=deque()\n",
    "        que1.append(root)\n",
    "        while 1:\n",
    "            if len(que1)==0:\n",
    "                return num\n",
    "            num = que1[0].val\n",
    "            while len(que1)!=0:\n",
    "                ptr=que1.popleft()\n",
    "                if ptr.left!=None:\n",
    "                    que2.append(ptr.left)\n",
    "                if ptr.right!=None:\n",
    "                    que2.append(ptr.right)\n",
    "            p=que2\n",
    "            que2=que1\n",
    "            que1=p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            current_level_size = len(queue)\n",
    "            for i in range(current_level_size):\n",
    "                node = queue.pop(0)\n",
    "                if i == 0:\n",
    "                    leftmost_value = node.val\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "    \n",
    "        return leftmost_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        st = deque([[root, 0]])\n",
    "        map_ = defaultdict(list)\n",
    "\n",
    "        while st:\n",
    "            cur, dep = st.popleft()\n",
    "            map_[dep].append(cur.val)\n",
    "            if cur.left:\n",
    "                st.append([cur.left, dep+1])\n",
    "            if cur.right:\n",
    "                st.append([cur.right, dep+1])\n",
    "        return map_[max(map_.keys())][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        ret = root.val\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                if i == 0 :ret = node.val\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        q = deque([root])\n",
    "\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "        \n",
    "        return node.val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        self.q = deque([root])\n",
    "        node = None\n",
    "        while self.q:\n",
    "            node = self.q.popleft()\n",
    "            if node.right:\n",
    "                self.q.append(node.right)\n",
    "            if node.left:\n",
    "                self.q.append(node.left)\n",
    "        return node.val\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        if root.left is None and root.right is None:\n",
    "            return root.val\n",
    "        level_map = {}\n",
    "        level = 0\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            stack = []\n",
    "            while queue:\n",
    "                stack.append(queue.pop(0))\n",
    "            while stack:\n",
    "                node = stack.pop(0)\n",
    "                if level not in level_map.keys():\n",
    "                    level_map[level] = []\n",
    "                level_map[level].append(node.val)\n",
    "                if node.left is not None:\n",
    "                    queue.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    queue.append(node.right)\n",
    "            \n",
    "            level += 1\n",
    "        print(\"level_map=\", level_map)\n",
    "        return level_map[max(level_map.keys())][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        maxd = 0\n",
    "        def dfs(root,dep):\n",
    "            nonlocal res,maxd\n",
    "            if not root:\n",
    "                return\n",
    "            if dep > maxd:\n",
    "                maxd = dep\n",
    "                res = root.val\n",
    "            dfs(root.left,dep+1)\n",
    "            dfs(root.right,dep+1)\n",
    "        dfs(root,1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        val = 0\n",
    "        maxDepth = 0\n",
    "        def dfs(node, depth):\n",
    "            if not node:\n",
    "                return None\n",
    "            # 看下一层的node\n",
    "            depth += 1\n",
    "            nonlocal val, maxDepth\n",
    "            if depth > maxDepth:\n",
    "                maxDepth = depth\n",
    "                val = node.val\n",
    "            dfs(node.left, depth)\n",
    "            dfs(node.right, depth)\n",
    "        dfs(root, 0)\n",
    "        return val\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        curVal = curHeight = 0\n",
    "        def dfs(node: Optional[TreeNode], height: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            \n",
    "            dfs(node.left, height+1)\n",
    "            dfs(node.right, height+1)\n",
    "            nonlocal curVal, curHeight\n",
    "            if height > curHeight:\n",
    "                curHeight = height\n",
    "                curVal = node.val\n",
    "        dfs(root, 1)\n",
    "        return curVal\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def impl(tree,count_deep,count_left):\n",
    "          if tree is None:\n",
    "              return (None,0,0)\n",
    "          if tree.left is None and tree.right is None:\n",
    "              return(tree.val,count_deep,count_left)\n",
    "          (l_val,l_deep,l_left) = impl(tree.left,count_deep+1,count_left+1)\n",
    "          (r_val,r_deep,r_left) = impl(tree.right,count_deep+1,count_left-1)\n",
    "          if l_deep > r_deep:\n",
    "              return (l_val,l_deep,l_left)\n",
    "          if l_deep < r_deep:\n",
    "              return (r_val,r_deep,r_left)\n",
    "          if l_left > r_left:\n",
    "              return (l_val,l_deep,l_left)\n",
    "          else:\n",
    "              return (r_val,r_deep,r_left)\n",
    "        return impl(root,0,0)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        curHeight = 0\n",
    "        curVal =root.val\n",
    "        def dfs(node: Optional[TreeNode], height: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            \n",
    "            dfs(node.left, height+1)\n",
    "            dfs(node.right, height+1)\n",
    "            nonlocal curVal, curHeight\n",
    "            if height > curHeight:\n",
    "                curHeight = height\n",
    "                curVal = node.val\n",
    "        dfs(root, 0)\n",
    "        return curVal\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        curVal = curHeight = 0\n",
    "        def dfs(node: Optional[TreeNode], height: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            height += 1\n",
    "            dfs(node.left, height)\n",
    "            dfs(node.right, height)\n",
    "            nonlocal curVal, curHeight\n",
    "            if height > curHeight:\n",
    "                curHeight = height\n",
    "                curVal = node.val\n",
    "        dfs(root, 0)\n",
    "        return curVal\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        curVal = curLength = 0\n",
    "\n",
    "        def dfs(root, height):\n",
    "            if not root:\n",
    "                return\n",
    "            height += 1\n",
    "            dfs(root.left, height)\n",
    "            dfs(root.right, height)\n",
    "            nonlocal curVal, curLength\n",
    "            if height > curLength:\n",
    "                curLength = height\n",
    "                curVal = root.val            #后续遍历，返回的这个节点就是最左边的叶子节点\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return curVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, None\n",
    "            left, l_val = dfs(node.left)\n",
    "            right, r_val = dfs(node.right)\n",
    "            if left >= right:\n",
    "                return left + 1, l_val if l_val is not None else node.val\n",
    "            else:\n",
    "                return right + 1, r_val if r_val is not None  else node.val\n",
    "        \n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        Deep = 0\n",
    "        ans = 0\n",
    "        def dfs(node, deep):\n",
    "            if not node:return\n",
    "            if node.left is None and node.right is None:\n",
    "                nonlocal Deep\n",
    "                if deep > Deep:\n",
    "                    nonlocal ans\n",
    "                    ans = node.val\n",
    "                    Deep = deep\n",
    "                    return\n",
    "\n",
    "            dfs(node.left, deep+1, )\n",
    "            dfs(node.right, deep+1)\n",
    "\n",
    "        dfs(root, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        return self.help(root)[0]\n",
    "        \n",
    "    def help(self, node):\n",
    "        if not node.left and not node.right:\n",
    "            return node.val, 1\n",
    "        else:\n",
    "            if not node.left:\n",
    "                v, h = self.help(node.right)\n",
    "                return v, h+1\n",
    "            else:\n",
    "                vl, hl = self.help(node.left)\n",
    "                if not node.right:                    \n",
    "                    return vl, hl+1\n",
    "                else:\n",
    "                    vr, hr = self.help(node.right)\n",
    "                    if hr > hl:\n",
    "                        return vr, hr+1\n",
    "                    else:\n",
    "                        return vl, hl+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        curVal = curHeight = 0\n",
    "        def dfs(node: Optional[TreeNode], height: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            height += 1\n",
    "            dfs(node.left, height)\n",
    "            dfs(node.right, height)\n",
    "            nonlocal curVal, curHeight\n",
    "            if height > curHeight:\n",
    "                curHeight = height\n",
    "                curVal = node.val\n",
    "        dfs(root, 0)\n",
    "        return curVal\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        val = 0\n",
    "        maxDepth = 0\n",
    "        def dfs(node, depth):\n",
    "            if not node:\n",
    "                return None\n",
    "            # 看下一层的node\n",
    "            depth += 1\n",
    "            nonlocal val, maxDepth\n",
    "            if depth > maxDepth:\n",
    "                maxDepth = depth\n",
    "                val = node.val\n",
    "            dfs(node.left, depth)\n",
    "            dfs(node.right, depth)\n",
    "        dfs(root, 0)\n",
    "        return val\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        depth = 1\n",
    "        val = root.val\n",
    "        \n",
    "        def dfs(node: TreeNode, d: int) -> None:\n",
    "            #print(f'calling dfs at node = {node}, d = {d}')\n",
    "            nonlocal depth\n",
    "            nonlocal val\n",
    "            if node.left == None and node.right == None:\n",
    "                if d > depth:\n",
    "                    val = node.val\n",
    "                    depth = d\n",
    "            else:\n",
    "                if node.left != None:\n",
    "                    dfs(node.left, d+1)\n",
    "                if node.right != None:\n",
    "                    dfs(node.right, d+1)\n",
    "        \n",
    "        dfs(root, 1)\n",
    "\n",
    "        return val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        curval = curheight = 0\n",
    "\n",
    "        def dfs(node: TreeNode, height: int)->int:\n",
    "            if not node: return None\n",
    "            height += 1\n",
    "            dfs(node.left,height)\n",
    "            dfs(node.right,height)\n",
    "            nonlocal curval,curheight\n",
    "            if height>curheight:\n",
    "                curheight = height\n",
    "                curval = node.val\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return curval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        curVal = curHeight = 0\n",
    "        def dfs(node:Optional[TreeNode], height:int)->None:\n",
    "            if node is None:\n",
    "                return\n",
    "            height += 1\n",
    "            dfs(node.left, height)\n",
    "            dfs(node.right, height)\n",
    "            nonlocal curVal, curHeight\n",
    "            if height > curHeight:\n",
    "                curHeight = height\n",
    "                curVal = node.val\n",
    "        dfs(root, 0)\n",
    "        return curVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        val = 0\n",
    "        maxDepth = 0\n",
    "        def dfs(node, depth):\n",
    "            if not node:\n",
    "                return None\n",
    "            # 看下一层的node\n",
    "            depth += 1\n",
    "            nonlocal val, maxDepth\n",
    "            if depth > maxDepth:\n",
    "                maxDepth = depth\n",
    "                val = node.val\n",
    "            dfs(node.left, depth)\n",
    "            dfs(node.right, depth)\n",
    "        dfs(root, 0)\n",
    "        return val\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    deep = -1\n",
    "    res = -1\n",
    "\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        def getFindBottomLeftValue(node: TreeNode, deepVal: int):\n",
    "            if node is None:\n",
    "                return\n",
    "            if deepVal > self.deep:\n",
    "                self.deep = deepVal\n",
    "                self.res = node.val\n",
    "                pass\n",
    "            getFindBottomLeftValue(node.left, deepVal + 1)\n",
    "            getFindBottomLeftValue(node.right, deepVal + 1)\n",
    "\n",
    "        pass\n",
    "        getFindBottomLeftValue(root, 0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        v = None\n",
    "        def bfs(ns: List[TreeNode]):\n",
    "            r = []\n",
    "            for n in ns:\n",
    "                if n.left:\n",
    "                    r.append(n.left)\n",
    "                if n.right:\n",
    "                    r.append(n.right)\n",
    "            if len(r) == 0:\n",
    "                nonlocal v\n",
    "                v = ns[0].val\n",
    "            else:\n",
    "                bfs(r)\n",
    "        bfs([root])\n",
    "        return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        def dfs(node, d):\n",
    "            if not node:\n",
    "                return\n",
    "            tmp1 = dfs(node.left, d+1)\n",
    "            tmp2 = dfs(node.right, d+1)\n",
    "            if not tmp1 and not tmp2:\n",
    "                return [node, d]\n",
    "            if not tmp1:\n",
    "                return tmp2\n",
    "            if not tmp2:\n",
    "                return tmp1\n",
    "            return tmp1 if tmp1[1] >= tmp2[1] else tmp2\n",
    "        ans = dfs(root, 0)\n",
    "        return ans[0].val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:\n",
    "        curVal = curHeight = 0\n",
    "        def dfs(node: Optional[TreeNode], height: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            height += 1\n",
    "            dfs(node.left, height)\n",
    "            dfs(node.right, height)\n",
    "            nonlocal curVal, curHeight\n",
    "            if height > curHeight:\n",
    "                curHeight = height\n",
    "                curVal = node.val\n",
    "        dfs(root, 0)\n",
    "        return curVal\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        self.leftval = list()\n",
    "\n",
    "        def dfs(root, depth):\n",
    "            if root:\n",
    "                if depth == len(self.leftval):\n",
    "                    self.leftval.append(root.val)\n",
    "                dfs(root.left, depth + 1)\n",
    "                dfs(root.right, depth + 1)\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return self.leftval[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        if not root.left:\n",
    "            if not root.right:\n",
    "                return root.val\n",
    "            else:\n",
    "                return self.help(root.right)[0]\n",
    "        else:\n",
    "            if not root.right:\n",
    "                return self.help(root.left)[0]\n",
    "            else:\n",
    "                vl, hl = self.help(root.left)\n",
    "                vr, hr = self.help(root.right)\n",
    "                if hr > hl:\n",
    "                    return vr\n",
    "                else:\n",
    "                    return vl\n",
    "    def help(self, node):\n",
    "        if not node.left and not node.right:\n",
    "            return node.val, 1\n",
    "        else:\n",
    "            if not node.left:\n",
    "                v, h = self.help(node.right)\n",
    "                return v, h+1\n",
    "            else:\n",
    "                vl, hl = self.help(node.left)\n",
    "                if not node.right:                    \n",
    "                    return vl, hl+1\n",
    "                else:\n",
    "                    vr, hr = self.help(node.right)\n",
    "                    if hr > hl:\n",
    "                        return vr, hr+1\n",
    "                    else:\n",
    "                        return vl, hl+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    max_dep = -inf\n",
    "    ans = 0\n",
    "    def findBottomLeftValue(self, root: TreeNode) -> int:\n",
    "        def dfs(root: TreeNode,depth:int):\n",
    "            if root is None:\n",
    "                return\n",
    "            if depth > self.max_dep:\n",
    "                self.max_dep = depth\n",
    "                self.ans =root.val\n",
    "            dfs(root.left,depth+1)\n",
    "            dfs(root.right,depth+1)\n",
    "        dfs(root,0)\n",
    "        return self.ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
